Sparsely populated data sets are utilized in numerous technical fields. The present invention was developed for efficiently encoding image data that has been transformed by successive applications of wavelet transforms, but is equally applicable to other types of sparsely populated data sets. Image data that has been transformed by successive applications of wavelet transforms tends to have large portions occupied by zero and near-zero values, especially if the data is subjected to a data quantization step prior to encoding.
The primary goals of the present invention are to provide an encoding methodology that (A) efficiently locates data tree branches that are entirely occupied by zero data and encoding such branches with as few data bits as possible, (B) determines the maximum number of data bits required to encode data tree branches that include at least some non-zero data, and (C) encodes non-zero data with the minimum number of data bits required to losslessly store such data.
Another goal of the present invention is to provide an encoding methodology that is computationally very efficient.